// https://www.lintcode.com/problem/valid-parentheses/description
// 423. 有效的括号序列
// 给定一个字符串所表示的括号序列，包含以下字符： '(', ')', '{', '}', '[' and ']'， 判定是否是有效的括号序列。

// 样例
// 括号必须依照 "()" 顺序表示， "()[]{}" 是有效的括号，但 "([)]"则是无效的括号。


// • [ ] ( [ ] { } ) 匹配
// • [ ] ( 不匹配
// • 经典栈应用问题，从左往右扫，左括号对应入栈 ，相匹配右括号对应出栈
// • 注意三种不匹配的情况：
// – a. 扫完后栈中还有元素
// – b. 扫描过程中栈是空的但还要执行出栈操作
// – c. 要执行出栈但是括号不匹配，比如 [)


class Solution {
public:
    /**
     * @param s: A string
     * @return: whether the string is a valid parentheses
     */
    bool isValidParentheses(string &s) {
        int len = s.length();
        int pos = 0;
        stack<char> char_stack;
        map<char, char> parentheses;
        
        // // 注意括号不能一起判断，要分别判断
        parentheses['('] = ')';
        parentheses['{'] = '}';
        parentheses['['] = ']';
        
        // 1. 不仅判断括号，包含其他的
        // while (pos < len)
        // {
        //     char t = s[pos];
        //     char_stack.push(t);
        //     if (t == ')' || t == '}' || t == ']')
        //     {
        //         char c = char_stack.top();
        //         while (c != '(' && c != '{' && c != '[')
        //         {
        //             char_stack.pop();
        //             if (char_stack.empty() || parentheses[char_stack.top()] != t)
        //             {
        //                 return false;
        //             }
        //             c = char_stack.top();
        //         }
        //         char_stack.pop();
        //     } 
        //     pos++;
        // }
        // return char_stack.empty();
        
        // 只判断括号序列，注意这种情况一对括号就直接拿出来了，
        // 和运算表达式处理不一样。因此新右括号只要和top()比较。
        while (pos < len)
        {
            char t = s[pos];
            if (t == '(' || t == '{' || t == '[')
            {
                char_stack.push(t);
            } 
            else if (char_stack.empty() || parentheses[char_stack.top()] != t)
            {
                return false;
            }
            else
            {
                char_stack.pop(); 
            }
            pos++;
        }
        return char_stack.empty();
    }
};